package Day2025_02_28;

import java.util.ArrayList;
import java.util.List;

public class LeetCode315 {
    int[] ret;
    int[] index;
    int[] tmpIndex;
    public List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        ret = new int[n];
        index = new int[n];
        tmpIndex = new int[n];
        for (int i = 0; i < n; i++) index[i] = i;
        mergeSort(nums, 0 , n - 1);
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) list.add(ret[i]);
        return list;
    }
    private void mergeSort (int[] nums, int left, int right) {
        if (left >= right) return;
        int mid = (right + left) >> 1;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        merge(nums, left, right, mid);
    }
    private void merge (int[] nums, int left, int right, int mid) {
        int s1 = left, e1 = mid;
        int s2 = mid + 1, e2 = right;
        int k = 0;
        int[] tmpArr = new int[right - left + 1];
        while (s1 <= e1 && s2 <= e2) {
            if (nums[s1] <= nums[s2]) {
                tmpIndex[k] = index[s2];
                tmpArr[k++] = nums[s2++];
            }
            else {
                ret[index[s1]] += e2 - s2 + 1;
                tmpIndex[k] = index[s1];
                tmpArr[k++] = nums[s1++];
            }
        }
        while (s1 <= e1) {
            tmpIndex[k] = index[s1];
            tmpArr[k++] = nums[s1++];
        }
        while (s2 <= e2) {
            tmpIndex[k] = index[s2];
            tmpArr[k++] = nums[s2++];
        }
        for (int i = 0; i < tmpArr.length; i++) {
            nums[left + i] = tmpArr[i];
            index[left + i] = tmpIndex[i];
        }
    }
}
